package com.lfg.leetcode.leetcode0;

public class No74searchMatrix {

    public static void main(String[] args) {
        int[][] array = new int[2][2];
//        int[][] array = new int[2][2];
        array[0] = new int[]{0, 1};
//        array[0] = new int[]{0, 1, 2, 3};
        array[1] = new int[]{3, 3};
//        array[1] = new int[]{5, 6, 7, 8};
//        array[2] = new int[]{9, 10, 11, 15};
        boolean ret = searchMatrix(array, 2);
        System.out.println("[" + ret + "]");
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length <= 0) {
            return false;
        }
        if (matrix[0].length <= 0) {
            return false;
        }
        int sx = 0;
        int sy = 0;
        int ex = matrix.length - 1;
        int ey = matrix[0].length - 1;
        int length = matrix[0].length;
        int li = ex * length + ey;

        while (true) {
            int si = sx * length + sy;
            int ei = ex * length + ey;
            if (si > ei || ei < 0 || si > li) {
                break;
            }
            int total = si + ei;
            int mid = (total + 1) / 2;
            int mx = mid / length;
            int my = mid % length;

            if (target == matrix[mx][my]) {
                return true;
            } else if (target > matrix[mx][my]) {
                mid++;
                sx = mid / length;
                sy = mid % length;
            } else {
                mid--;
                ex = mid / length;
                ey = mid % length;
            }
        }
        return false;
    }
}

